/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package Entidades;

import java.util.ArrayList;

/**
 *
 * @author Marco
 */
public abstract class Grafo {
    
    protected Nodo[] nodos; // vector de nodos

    public Nodo[] getNodos() {
        return nodos;
    }
    protected Arco[][] adyacencia; //vector de adyacencia
    // requerido por el algoritmo de Warshall
     public boolean  [][]trans;  // matriz para almacenar el cierre transitivo
    //devuelve la cantidad de nodos actual que tiene lalista  es par aprobarç
    public int cantidadDeNodos(){
        int total=0;
        for(int i =0; i < nodos.length;i++){
            if(nodos[i]!=null)
            total++;
        }
        return total;
    }   
    public int cantidadArcos(){
        int i, j, n = nodos.length;
        int k =0;
           for (i = 0; i<n; i++)
           {
             for (j = 0; j < n; j++)
             {
                 if(adyacencia[i][j].isExiste())
                     k++;
             }
           }
        
           return k;
    }
    public Grafo (){
        //eduardo estvup aqui
       nodos = new Nodo[25];
       adyacencia = new Arco [25][25];
       
        for(int i = 0; i < 25; i++)
           {
               for(int j = 0; j < 25; j++)
               {
                   //... llena de Arcos con "existe" valiendo false
                   adyacencia[i][j] = new Arco();
               }
           }
        // la matriz de cierre transitivo, con todos sus casilleros valiendo false...
           trans = new boolean [25][25];
    }
    
    
     /**
      * Indica la cantidad de nodos representados en este grafo.
      * @return la cantidad de nodos del grafo.
      */
     public int length()
     {
        return nodos.length;   
     }
    
     /*se redefine en las clases hijas*/
    public abstract boolean unir(int nodoInicial, int nodoFinal);
    /*se redefine en las clases hijas*/
    public abstract boolean cortar(int nodoInicial, int nodoFinal);
    
    /**
     * Recibe como parametro el nombre de un nodo generado en la UI y retorna la
     * posicion del  Nodo al que pertenece, si no encuentra retorna -1
     * por el auto incremento, los nodos de la UI nunca tendran el mismo nombre
     * @param nombre
     * @return 
     */
    public int buscarNodo(int nombre){
    
        if(nodos[0]!=null){
            for (int i=0; i<nodos.length; i++) 
                   { 
                       if ( nodos[i].getNombre()==nombre ) return i; 
                   }
        }
        return -1;
    }
    
    
    public boolean hayArco(int nodoInicial, int nodoFinal){
        boolean out = false;
       int i1 = buscarNodo (nodoInicial);
       int i2 = buscarNodo (nodoFinal);
       if( i1 != -1 && i2 != -1 )
       {
          out = adyacencia[i1][i2].isExiste();
       }
       return out;
    
    }
    /**
     * busca el peso del arco que une los dos nodos pasados por parametro
     * si no encuentra un arco entre los dos nodos devuelve -2 ;-1 significa que 
     * el arco no tiene peso configurado, esto e spor que aceptamso valor de peso 0
     * @param nodoInicial
     * @param nodoFinal
     * @return 
     */
       public int getPesoArco ( int nodoInicial, int nodoFinal )
     {
       int out = -2;
       int i1 = buscarNodo (nodoInicial);
       int i2 = buscarNodo (nodoFinal);
       if( i1 != -1 && i2 != -1 )
       {
          if(adyacencia[i1][i2].isExiste())// si hay arco que devuelva el peso, sino -2 
          out = adyacencia[i1][i2].getPeso();
       }
       return out;
     }
    /*
     * metodo para obtener el peos de un nodo, si no encuentra el nodo devuelve menos 2
     * si devuelve -1 signifca que el nodo no esta ponderado
     */   
    public int getPesoNodo(int nodoAEvaluar){
        int out = -2;
         int i1 = buscarNodo(nodoAEvaluar);
         if(i1!=-1){
           out=nodos[i1].getPeso();
         }
         return out;
    }
   /**
    * Metodo que permite agregar un nodo al grafo, siempre y cuando haya lugar
    * hy te pone el nombre segun el lugar donde se ageg
    * @param nuevoNodo
    * @return 
    */
    
        
    public int agregarNodo(Nodo nuevoNodo){
        if(nuevoNodo!=null){
            for (int i=0; i<nodos.length; i++)
           { 
               if(nodos[i] == null)
               {
                  nuevoNodo.nombre=i;
                  nodos[i] = nuevoNodo;
                  return i;
               }
           }
        }
       return -1;
    }
    /**
     * recibe como parametor el numero de nodo a elimian y lo elimina
     * funciona porque los ndos se llama n numericamente
     * @param nroNodo 
     */
     public void eliminarNodo(int nroNodo){
      nodos[nroNodo]=null;
      for(int j=0;j<25;j++){
          adyacencia[nroNodo][j].setExiste(false);
      }
      for(int j=0;j<25;j++){
          adyacencia[j][nroNodo].setExiste(false);
      }
    }
   
   /**
    * metodo para ponderar un arco, recibe como parametro los nombres de los nodso que 
    * forman ese arco
    * @param nodoInicial
    * @param nodoFinal
    * @param peso
    * @return 
    */ 
   public boolean ponderarArco(int nodoInicial, int nodoFinal,int peso){
       
       boolean out = false;
       int i1 = buscarNodo (nodoInicial);
       int i2 = buscarNodo (nodoFinal);
       if( i1 != -1 && i2 != -1 )
       {
          adyacencia[i1][i2].setPeso(peso);
          adyacencia[i2][i1].setPeso(peso);
          out= true;
       }
       return out;
   }
   /**
    * Metodo para ponderar un nodo, recibe como parametro el numero de nodo
    * desde la UI
    * @param nodoAPonderar
    * @param peso
    * @return 
    */
   public boolean ponderarNodo(int nodoAPonderar,int peso){
     boolean out=false;
     int i1 = buscarNodo(nodoAPonderar);
     if(i1!=-1){
          nodos[i1].setPeso(peso);
          out=true;
     }
     return out;
   }
   /**
    * Si hay algoritmos de resolucion que se aplican a ambos tipos de
    * grafos entocnes los metodos pueen ir aca
    */         
   public void caminosXWarshall ()
     {
           int i, j, k, n = nodos.length;
           for (i = 0; i<n; i++)
           {
             for (j = 0; j < n; j++)
             {
                 trans[i][j] = adyacencia[i][j].isExiste();
             }
           }
    
           for (k = 0; k < n; k++)
           {
                 for (i = 0; i < n; i++)
                 {
                       if ( trans[i][k] )
                       {
                           for (j = 0; j < n; j++) { trans[i][j] = trans[i][j] || trans[k][j]; }
                       }
                 }
           }
     }
   
   public boolean [][]getCaminoMarchall()
     {
        return trans;
     }
   /////////////ALGORITMOS///////////////////
        public ArrayList<Integer> buscarAEM()
    { 
           ArrayList<Integer> aMET = new ArrayList<Integer>(); 
           int n = nodos.length;
           int k, t, suma  = 0, min = n;        // la casilla [n] se usa como bandera...
           int visitados[] = new int[n + 1];    // uno más que la máxima cantidad de nodos...
           int padre[] = new int [n];           // indice del padre del nodo que entra al árbol
           int novisto = -10000;                // se usa como bandera, conviene un valor "grande"...
    
           for (k = 0; k < n; k++)
           {
                visitados[k] = novisto; // no vi a nadie todavia...
                padre[k] = -1;          // ... y por lo tanto tampoco hay padres
           }
    
           visitados[n] = novisto - 1; // se usa como bandera para buscar el minimo peso
           for (k = 0; k != n; k = min , min = n)
           {
                visitados[k] = - visitados[k];
                if (visitados[k] == - novisto) visitados[k] = 0;
                for (t = 0; t < n; t++)
                {
                     if (visitados[t] < 0)
                     {
                        int prioridad = adyacencia[k][t].getPeso(); 
                        if (adyacencia[k][t].isExiste() && visitados[t] < -prioridad)
                        {
                           visitados[t] = -prioridad;
                           padre[t] = k;
                        }
                        if (visitados[t] > visitados[min]) min = t;
                     }
                }
           }
           
           
           StringBuffer sb = new StringBuffer("Un AEM, contiene los arcos siguientes:\n\n");
           for (k = 1; k < n; k++)
           {
                 int i1 = padre[k];
                 if(i1==-1){
                     break;
                 }
                 aMET.add(nodos[i1].getNombre());
                 aMET.add(nodos[k].getNombre());
                
                 suma += visitados[k];
           }
           
           
           return aMET;
           
    }
    /**
     *  Determina cuántas componentes conexas tiene el grafo, recorriendo el mismo en profundidad.
     *  @return la cantidad de componentes conexas del grafo.
     */ 
    public int contarConexasEnProfundidad ()
    { 
          int k, cx = 0, n = nodos.length;
          boolean []visitados = new boolean[n];
            
          //aplica el recorrido...
          for (k=0; k<n; k++)
          {   
               if ( ! visitados[k] ) 
               {
                      // encontro una nueva componente conexa...
                      // ... la cuenta y la recorre en profundidad...
                      cx++;
                      visitarEnProfundidad(k, visitados);
               }
          }
          return cx;
    }
      private void visitarEnProfundidad (int k, boolean []visitados)
    {
         int t, n = nodos.length;
         visitados[k] = true;
         for (t=0; t<n; t++)
         {
            if( adyacencia[k][t].isExiste() )
            {
                if ( ! visitados[t] ) visitarEnProfundidad(t, visitados);
            }
         }
    }
      
       /**
     * Calcula el "camino m�s corto" (o sea, el de menor sumatoria de pesos) desde un nodo tomado como par�metro a 
     * cada uno del resto de los nodos del grafo, mediante el algoritmo de Dijkstra. 
     * @param nodoinicio el nodo desde el cual se calculan las distancias m�nimas.
     * @return una cadena representando el contenido del �rbol de expansi�n m�nimo calculado
     */
    public String buscarCMC( int nodoinicio )
    {  
          int n = nodos.length;
          int k, t, inicio, suma = 0, min = n; // la casilla [n] se usa como bandera...
          int visitados[] = new int [n + 1];   // uno mas que la maxima cantidad de nodos...
          int padre[] = new int[n];            // indice del padre del nodo que entra al arbol
          int novisto = -10000;                // se usa como bandera, conviene un valor "grande"...

          for (k = 0; k < n; k++)
          {
               visitados[k] = novisto;  // no vi a nadie todavia...
               padre[k] = -1;           // ... y por lo tanto npoco hay padres
          }
    
          visitados[n] = novisto - 1; // se usa como bandera para buscar el minimo peso
          inicio = buscarNodo(nodoinicio);
          if (inicio == -1) return "No existe el nodo inicial dado...";
          
          for (k = inicio; k != n; k = min , min = n)
          {
               visitados[k] = - visitados[k];
               if (visitados[k] == - novisto) visitados[k] = 0;
               for (t = 0; t < n; t++)
               {
                     if (visitados[t] < 0)
                     {
                        int p = adyacencia[k][t].getPeso(); 
                        int prioridad = visitados[k] + p;
                        if (adyacencia[k][t].isExiste() && visitados[t] < -prioridad)
                        {
                               visitados[t] = -prioridad;
                               padre[t] = k;
                        }
                        if (visitados[t] > visitados[min]) min = t;
                     }
               }
          }

         // StringBuffer sb = new StringBuffer("Los caminos minimos desde " + nodoinicio + " hasta los otros nodos son:\n\n");
          String aux="Los caminos minimos desde " + nodoinicio + " son:\n";
          for (k = 0; k < n; k++)
          {
              if (nodos[k]==null) break;
               if (k != inicio)
               {
                     int i1 = padre[k];
                     aux+=" El camino desde "+ nodos[k].getNombre()+" a "+nodoinicio+" pasa por los nodos:{ ";
                    
                  
                     while(i1 != -1)
                     {
                         aux+= nodos[i1].getNombre()+" ";
                  
                            i1 = padre[i1];
                     }
                     aux+="}\n";
                     
               }
          }
          return aux;
    }

    
    

}
